package com.jz.algorithm.Array;

import java.util.*;
import java.util.stream.Stream;



/**
 * @Classname ArraySeries
 * @Description 数组相关的题目
 * @Date 2021/10/19 14:55
 * @Author Jz
 * @Version 1.0
 */
public class ArraySeries {

    /**
     * @Methodname removeTarget
     * @Description 移除数组中等于target值的元素，并返回数组的长度
     * @Date 2021/10/19 14:57
     * @Author Jz
     * @Return 移除后数组的长度
     * @Param array数组，target目标值
     */

    public int removeTarget(int[] array, int target) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < array.length; fastIndex++) {
            if (array[fastIndex] != target) {
                array[slowIndex] = array[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;

    }

    /**
     * @Methodname removeDuplcate
     * @Description 删除一个有序数组里面重复的元素，返回删除后数组的长度，不要使用额外空间 LeetCode 26
     * @Date 2021/10/19 16:28
     * @Author Jz
     * @Return
     * @Param
     */
    public int removeDuplcate(int[] nums) {

        int slowIndex = 0;
        int fastIndex = 1;
        while (fastIndex < nums.length) {
            if (nums[slowIndex] == nums[fastIndex]) {
                fastIndex++;
            } else {
                nums[slowIndex + 1] = nums[fastIndex];
                fastIndex++;
                slowIndex++;
            }
        }
        return slowIndex;


    }

    /**
     * @Methodname containsDuplicate
     * @Description 判断一个数组中是否存在相同的元素，有返回true，没有返回fasle
     * @Date 2021/10/20 13:14
     * @Author Jz
     * @Return Boolean true,fasle
     * @Param nums 数组
     */
    public boolean containsDuplicate(int[] nums) {

        HashSet<Integer> integers = new HashSet<Integer>();

        for (int i = 0; i < nums.length; i++) {

            if (integers.contains(nums[i])) {
                return true;
            } else {
                integers.add(nums[i]);
            }
        }
        return false;
    }

    /**
     * @Methodname moveZeroes
     * @Description 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序
     * @Date 2021/10/20 13:24
     * @Author Jz
     * @Return 无返回值
     * @Param 数组
     * @Example 输入: [0,1,0,3,12],输出: [1,3,12,0,0]
     */
    public static void moveZeroes(int[] nums) {

        for (int i = 0; i < nums.length; i++) {

            if (nums[i] == 0) {
                for (int j = i + 1; j < nums.length; j++) {
                    if (nums[j] != 0) {
                        int temp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = temp;
                        break;
                    }

                }
            }

        }

    }

    /**
     * @Methodname moveZeroes2
     * @Description 上面一题第二种解法
     * @Date 2021/10/20 14:16
     * @Author Jz
     * @Return null
     * @Param 数组
     */
    public static void moveZeroes2(int[] nums) {
        int j = 0;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }

        }
        for (int m = j; m < nums.length; m++) {

            nums[m] = 0;
        }


    }


    /**
     * @Methodname sortedSquares
     * @Description 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
     * @Date 2021/10/20 16:24
     * @Author Jz
     * @Return 返回后的数组
     * @Param 入参数组
     * @Example 输入：nums = [-4,-1,0,3,10]
     * 输出：[0,1,9,16,100]
     * 解释：平方后，数组变为 [16,1,0,9,100]
     * 排序后，数组变为 [0,1,9,16,100]
     */
    public int[] sortedSquares(int[] nums) {
        Stream<int[]> nums1 = Stream.of(nums);
        int[] ints = Arrays.stream(nums).map(i -> i * i).sorted().toArray();
        return ints;
    }

    /**
     * @Methodname sortedSquares2
     * @Description 双指针解法
     * @Date 2021/10/26 14:33
     * @Author Jz
     * @Return 新的数组
     * @Param 原始数组
     */
    public int[] sortedSquares2(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int[] b = new int[nums.length];
        int length = right;

        while (left <= right && length >= 0) {
            if (nums[right] * nums[right] > nums[left] * nums[left]) {
                b[length] = nums[right] * nums[right];
                right--;
                length--;
            } else {
                b[length] = nums[left] * nums[left];
                length--;
                left++;
            }

        }

        return b;
    }


    /**
     * @Methodname minSubArrayLen
     * @Description 给定一个含有 n 个正整数的数组和一个正整数 target 。
     * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
     * leetcode 209
     * @Date 2021/10/27 9:24
     * @Author Jz
     * @Return 最小数组的长度
     * @Param target 目标值，nums 数组
     */
    public static int minSubArrayLen(int target, int[] nums) {
        int sum = 0;
        int p = 0;
        int q = 0;
        int count = Integer.MAX_VALUE;
        while(p<nums.length){
            sum+=nums[p++];
            while(sum>=target){
                count=Math.min(count,p-q);
                sum-=nums[q++];
            }
        }
        return count==Integer.MAX_VALUE?0:count;
    }
    public static   int minSubArrayLen3(int s, int[] nums) {
        int lo = 0, hi = 0, sum = 0, min = Integer.MAX_VALUE;
        while (hi < nums.length) {
            sum += nums[hi++];
            while (sum >= s) {
                min = Math.min(min, hi - lo);
                sum -= nums[lo++];
            }
        }
        return min == Integer.MAX_VALUE?0:min;
    }

    public static int minSubArrayLen2(int target, int[] nums) {

        int sum = 0;
        int p = 0;
        int q = 0;
        int count = 0;
        ArrayList<Integer> integers = new ArrayList<>();

       while(p<nums.length){
            if (p != nums.length && nums[p] >= target) {
                return 1;
            }
            while (sum >= target) {
                integers.add(count);
                sum = sum - nums[q];
                q++;
                count--;

            }
            while (sum < target && p < nums.length) {
                sum = sum + nums[p];
                p++;
                count++;

            }


        }
        if (integers.size() != 0) {
            Collections.sort(integers);
            return integers.get(0) == null ? 0 : integers.get(0);
        }
        else {
            return 0;
        }


    }

    /**
     * @Methodname minWindow
     * @Description 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     * 注意：
     * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
     * 如果 s 中存在这样的子串，我们保证它是唯一的答案
     * @Date 2021/10/28 16:29
     * @Author Jz
     * @Return 最小字符串
     * @Param s t
     */
    public static String minWindow(String s, String t) {

        if (s == null || s.length() == 0 || t == null || t.length() == 0){
            return "";
        }
        int[] need = new int[128];
        //记录需要的字符的个数
        for (int i = 0; i < t.length(); i++) {
            need[t.charAt(i)]++;
        }
        //l是当前左边界，r是当前右边界，size记录窗口大小，count是需求的字符个数，start是最小覆盖串开始的index
        int l = 0, r = 0, size = Integer.MAX_VALUE, count = t.length(), start = 0;
        //遍历所有字符
        while (r < s.length()) {
            char c = s.charAt(r);
            if (need[c] > 0) {//需要字符c
                count--;
            }
            need[c]--;//把右边的字符加入窗口
            if (count == 0) {//窗口中已经包含所有字符
                while (l < r && need[s.charAt(l)] < 0) {
                    need[s.charAt(l)]++;//释放右边移动出窗口的字符
                    l++;//指针右移
                }
                if (r - l + 1 < size) {//不能右移时候挑战最小窗口大小，更新最小窗口开始的start
                    size = r - l + 1;
                    start = l;//记录下最小值时候的开始位置，最后返回覆盖串时候会用到
                }
                //l向右移动后窗口肯定不能满足了 重新开始循环
                need[s.charAt(l)]++;
                l++;
                count++;
            }
            r++;
        }
        return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
    }
    public static String minWindow2(String s, String t) {


        if (s == null || s.length() == 0 || t == null || t.length() == 0){
            return "";
        }

        HashMap<Character, Integer> stringIntegerHashMap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            if (stringIntegerHashMap.containsKey(t.charAt(i))){
                Integer integer = stringIntegerHashMap.get(t.charAt(i));
                stringIntegerHashMap.put(t.charAt(i),integer.intValue()+1);
            }
            else {
                stringIntegerHashMap.put(t.charAt(i),1);
            }
        }
        int p=0;
        int q=0;
        int count=0;
        int tempP=0;


        HashMap<Object, Integer> objectObjectHashMap = new HashMap<>();
        while(p<s.length()){

            if (stringIntegerHashMap.containsKey(s.charAt(p))){
                    Integer integer = stringIntegerHashMap.get(s.charAt(p));
                    stringIntegerHashMap.put(s.charAt(p),integer-1);
            }
            p++;
            while(checkToZero(stringIntegerHashMap)){
                if (p-q<=count){
                    count=p-q;
                    objectObjectHashMap.put("count",count);
                    objectObjectHashMap.put("p",q);
                }

                if (stringIntegerHashMap.containsKey(s.charAt(q))){
                        stringIntegerHashMap.put(s.charAt(q),stringIntegerHashMap.get(s.charAt(q))+1);
                }
                q++;

            }

        }


        return s.substring(objectObjectHashMap.get("p"),objectObjectHashMap.get("count")+objectObjectHashMap.get("p"));
    }

    private static boolean checkToZero(HashMap<Character, Integer> stringIntegerHashMap) {
        boolean a = true;
        for (Map.Entry<Character, Integer> characterIntegerEntry : stringIntegerHashMap.entrySet()) {
            if (characterIntegerEntry.getValue().intValue()>0) {
                a=false;
            }
        }
        return a;
    }


    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 2, 4, 3 };
       String s="ab"; String t="A";
        System.out.println(minWindow2(s, t));
        //   System.out.println("a".equals("A"));

    }


}
